#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Interval {
     int start;
     int end;
     Interval() : start(0), end(0) {}
     Interval(int s, int e) : start(s), end(e) {}
};


void changeLayer(int delta, int point, int &curLayer, vector<Interval> &res){
	int oldLayer = curLayer;
	curLayer += delta;
	if(oldLayer == 0 && curLayer > 0 ){
		if(res.size()>0 && res[res.size()-1].end == point){

		}
		else{
			Interval newInterval(point, 0x7FFFFFFF);
			res.push_back(newInterval);
		}

	}
	else if(oldLayer > 0 && curLayer == 0){
		res[res.size()-1].end = point;
	}
	return;
}



vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	
	int curLayer = 0;
	int insertPointIndex = 0; // 0 for begin 1 for end 2 for none
	vector<Interval> res;
	int curPointIndex = 0;  // 0 for begin 1 for end
	int insertDeltaLayer = 1;
	int curInsertPoint = newInterval.start;

	int i = 0;
	while(i < intervals.size()){
		int deltaLayer = 0;
		int curPoint = 0;
		if(curPointIndex == 0){
			deltaLayer = 1;
			curPoint = intervals[i].start;
		}
		else{
			deltaLayer = -1;
			curPoint = intervals[i].end;
		}
		if(insertPointIndex != 2){
			if(curPoint <= curInsertPoint){
				// do change layer
				changeLayer(deltaLayer, curPoint, curLayer, res);
				if(curPointIndex == 0){
					curPointIndex = 1;
				}
				else{
					++i;
					curPointIndex = 0;
				}
			}
			else{
				// do change layer
				changeLayer(insertDeltaLayer, curInsertPoint, curLayer, res);
				if(insertPointIndex == 0){
					insertPointIndex = 1;
					curInsertPoint = newInterval.end;
					insertDeltaLayer = -1;
				}
				else if(insertPointIndex == 1){
					insertPointIndex = 2;
				}
			}
		}
		else{
			// change layer
			changeLayer(deltaLayer, curPoint, curLayer, res);
			if(curPointIndex == 0){
				curPointIndex = 1;
			}
			else{
				curPointIndex = 0;
				++i;
			}
		}
	}
	if(insertPointIndex != 2){
		if(insertPointIndex == 0){
			changeLayer(1, newInterval.start, curLayer, res);
			changeLayer(-1, newInterval.end, curLayer, res);
		}
		else{
			changeLayer(-1, newInterval.end, curLayer, res);
		}
	}
	return res;
}


int main(){
	vector<Interval> tmp;
	tmp.push_back(Interval(1,3));
	//tmp.push_back(Interval(3,9));
	vector<Interval> res = insert(tmp, Interval(3,10));
	for(int i=0; i<res.size(); ++i){
		cout<< res[i].start << '-' << res[i].end <<endl;
	}

	

}